package com.hkb.josephusproblemlib;

/**
 * 循环链表解决约瑟夫问题方案
 *
 * @author hkb
 * @since 2020年5月28日22:52:51
 */

public class Main {
    private static class Person {
        private int data;
        private Person next;

        public Person(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        int N = 24;//表示总个数
        int M = 3;//数到几出列

        //头节点单列出来，方便形成循环链表
        Person firstPerson = new Person(1);
        Person x = firstPerson;

        //建立单向链表
        for (int i = 2; i <= N; i++) {
            x = (x.next = new Person(i));
        }

        //最后一个节点的next指向第一个节点，形成循环链表
        x.next = firstPerson;
        System.out.println("依次杀掉的顺序为：");
        //循环递归到链表
        while (x != x.next) {
            //找到第M个人
            for (int i = 1; i < M; i++) {
                x = x.next;
            }
            //杀掉第M个人
            System.out.print(x.next.data + " ");
            //链表归零
            x.next = x.next.next;
        }
        System.out.println();
        System.out.println("最后或者的是： " + x.data);
    }
}
